package question1_5;

/**
 * @description:
 * 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * [
 *   [1,2,8,9],
 *   [2,4,9,12],
 *   [4,7,10,13],
 *   [6,8,11,15]
 * ]
 * 给定 target = 7，返回 true。
 *
 * 给定 target = 3，返回 false。
 * @author: jhy
 * @time: 2021/5/19 9:32
 */
public class Question4 {

    public static void main(String[] args) {

        //int[][] array = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
        int[][] array = {{1,1}};
        Question4 question4 = new Question4();
        //boolean b = question4.Find1(7, array);
        //boolean b = question4.Find2(7, array);
        boolean b = question4.Find3(7, array);
        System.out.println(b);

    }


    //第一种：暴力寻找
    public boolean Find1(int target, int [][] array) {
        for(int i = 0;i < array.length;i++){
            for(int j = 0;j < array[0].length;j++){
                if(array[i][j] == target){
                    return true;
                }
            }
        }
        return false;
    }

    //第二种：定义一个二分查找一维数组的方法，对每一个可能出现target的行进行二分查找
    public boolean Find2(int target, int [][] array) {
        if(array == null ||array.length == 0 || array[0].length == 0){
            return false;
        }
        //对每一行进行二分查找
        for(int i = 0;i < array.length;i++){
            if(array[i][0] <= target && array[i][array[0].length - 1] >= target){
                if(binarySearch(target,array[i])){
                    return true;
                }
            }
        }
        return false;
    }


    //二分查找一维数组的方法
    public boolean binarySearch(int target,int[] array){

        int i = 0;
        int j = array.length - 1;
        while (i <= j){
            int mid = (j + i) / 2;
            if(array[mid] > target){  //中间值大于目标值，向左查找
                j = mid - 1;
            }else if(array[mid] < target){ //中间值小于目标值，向右查找
                i = mid + 1;
            }else {
                return true;
            }
        }
        return false;
    }


    //第三种方法：剑指offer推荐的方法
    //选取数组右上角的数字。如果该数字等于要查找的数字，则查找过程结束
    //如果该数据大于要查找的数据，则剔除这个数字所在的列
    //如果该数据小于要查找的数据，则剔除这个数字所在的行
    //直到找到要查找的数字，或者查找范围为空
    public boolean Find3(int target, int [][] array) {
        if(array == null || array.length == 0 || array[0].length == 0){
            return false;
        }

        //数组的行数
        int row = array.length;
        //数组的列数
        int col = array[0].length;
        //右上角的数字坐标(i,j)
        int i = 0;
        int j = col - 1;
        while (i < row && j >= 0){

            //如果当前查找范围右上角的数据等于要查找的数字，结束
            if(array[i][j] == target){
                return true;
            }else if(array[i][j] > target){
                //当前查找范围右上角的数据大于要查找的数字，剔除该列(最右边的列)
                j -= 1;
            }else {
                //如果查找范围右上角的数据小于要查找的数据，则剔除这个数字所在的行
                i += 1;
            }
        }
        return false;
    }

    /*
    为什么选择右上角数字进行比较，因为每一行和每一列都是递增的，
    右上角的数据相对于该行来说是最大的，相对于该列来说是最小的，每一次比较肯定可以缩小查找范围
    根据这个理解，也可以选取左下角数字进行比较
     */

}
